package leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author wangmaolin1
 * @date 2021/12/26 下午7:08
 */
public class _111树的最小深度 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        int i = minDepth3(treeNode);
        System.out.println(i);
    }
    public static  int minDepth3(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth=0;
        while (!q.isEmpty()){
            int size = q.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode temp = q.poll();
                if (temp.left ==null && temp.right == null){
                    return depth;
                }
                if (temp.left!=null){
                    q.offer(temp.left);
                }
                if (temp.right!=null){
                    q.offer(temp.right);
                }
            }
        }
        return depth;
    }
    /**
     * 注意点：平衡二叉树的定义是，每个节点的左右子树的绝对值都不超过1
     * 自顶向下
     * @param root
     * @return
     */
    public  int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        int min=Integer.MAX_VALUE;
        if (root.left!=null){
            min=Math.min(min,minDepth(root.left));
        }
        if (root.right!=null){
            min=Math.min(min,minDepth(root.right));
        }
        return min+1;
    }

    /**
     * bfs
     * @param root
     * @return
     */
    public  int minDepth2(TreeNode root) {
        if (root==null){
            return 0;
        }
        Queue<QueueNode>ququq=new LinkedList<>();
        ququq.offer(new QueueNode(root,1));
        while (!ququq.isEmpty()){
            QueueNode node = ququq.poll();
            if (node.node.left==null&&node.node.right==null){
                return node.height;
            }
            if (node.node.left!=null){
                ququq.offer(new QueueNode(node.node.left,node.height+1));
            }
            if (node.node.right!=null){
                ququq.offer(new QueueNode(node.node.right,node.height+1));

            }
        }
        return 0;
    }
    public static class QueueNode{
        TreeNode node;
        int height;

        public QueueNode(TreeNode node, int height) {
            this.node = node;
            this.height = height;
        }
    }


}
